package 力扣.栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class 每日温度739 {
    public static void main(String[] args) {
//        int[] temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
//        int[] temperatures = {73,70,60,50,40};
        int[] temperatures = {73,80,90,66,100};
        int[] ints = dailyTemperatures2(temperatures);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 栈
     * 原理；遍历数组，判断栈中元素和今日温度，若小于则出栈并计算日差，然后比较两个临近的温度，如果前者小于后者，得出日差为1，否则前者入栈。
     *      但是‘临近比较’总会‘顾首不顾尾’。最后还要比较最后一个元素和栈中剩余的元素
     * @param T
     * @return
     */
    public static int[] dailyTemperatures(int[] T) {
        Deque<Integer> st = new LinkedList<Integer>();
        for (int i = 0; i < T.length - 1; i++) {
              while (!st.isEmpty()){
                    if ( T[st.peek()] < T[i]){//栈中的元素 是否有比 今日气温低的
                        int te =st.pop();//出栈
                        T[te] = i-te;//计算日差
                    }else break;
              }
              if (T[i + 1] > T[i]){
                  T[i] = 1;
              }else {
                  st.push(i);//入栈
              }
        }
        // 处理最后一个元素 以及 栈中剩余的元素
        st.push(T.length-1);
        int last = T[T.length - 1];
        while (!st.isEmpty()){
            if (T[st.peek()] < last){
                int te = st.pop();
                T[te] = T.length-1 - te;
            }else {
                T[st.pop()] = 0;
            }
        }
        return T;
    }

    /**
     * 栈
     * 原理：遍历数组，让数组元素（每日温度）的下标入栈，若当日温度大于栈中的温度，则出栈并求出日差，直到数组遍历完毕就可得到结果
     * @param T
     * @return
     */
    public static int[] dailyTemperatures2(int[] T) {
            int length = T.length;
            int[] ans = new int[length];
            Deque<Integer> stack = new LinkedList<Integer>();
            for (int i = 0; i < length; i++) {
                int temperature = T[i];
                while (!stack.isEmpty() && temperature > T[stack.peek()]) {// 栈非空 && 栈中的温度 小于当前温度
                    int prevIndex = stack.pop();//出栈
                    ans[prevIndex] = i - prevIndex;//日差
                }
                stack.push(i);//数组元素的下标依次入栈
            }
            return ans;//最后一个元素不用比较直接为0，在数组赋值时就弄好了。
        }
}
